为了浅显易懂,本文对很多简单的推导都加以说明,尽量减少跳步,尽管有些可能很好想到。所以略显冗长。
已知全集
我们这里用
如何生成?先上代码:
vector<int> generate_sub_set(int x) {
vector<int> ret;
for(int p=x;p;p=(p-1)&x) ret.push_back(p);
ret.push_back(0) // 特殊处理空集
return ret;
}
每次生成
关键代码就一行,很短,不是吗?
下面来证明这个的正确性(变量沿用上文,
命题1:
证明:我们使用了按位与
命题2:枚举过程中不存在重复的集合。
证明:首先我们知道
命题3:枚举过程中不存在遗漏的集合。
证明:根据命题2,由于
设
这个过程是根据减法的退位得到的,不必再证明了吧。
因而
因此我们可以只看后
命题3得证。
综合上述三个命题,正确性便显然了。
通过这个方法我们枚举的上限复杂度
那有什么用呢?
当生成
一个暴力的想法是,直接枚举
for(int x=0,ed=(1<<n);x<ed;++x)
for(int s=0;s<ed;++s)
if(s|x==x) cout<<s<<' ';
优化的方法也挺暴力的,就是通过刚才提到的生成子集的方法:
for(int x=0,ed=(1<<n);x<ed;++x) {
for(int p=x;p;p=(p-1)&x) cout<<p<<' ';
cout<<0<<' ';
}
复杂度是多少呢?
我们知道中间这个循环是
发现顺序不重要。我们只需要统计对于每个
那么就是:
根据二项式定理,这个式子等于
因此这个做法的复杂度是
其实这个还有一个证明。很简单。设要求
对于每一个元素,都只有把它放到